/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-10-11
 * Time: 18:29
 */
public class test4 {
    public static void main(String[] args) {
        System.out.println("4");
    }
    /*
    LeetCode86 分隔链表  给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
     */

    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode large = new ListNode(0);
        ListNode smallHead = small;
        ListNode largeHead = large;
        while(head!=null){
            if(head.val<x){
                small.next = head;
                small = small.next;
            }else{
                large.next=head;
                large = large.next;
            }
            head=head.next;
        }
        large.next=null;
        small.next=largeHead.next;
        return smallHead.next;
    }
}
